package com.dataStructure.并查集;

@SuppressWarnings("all")
public class 并查集_QuickUnion extends 并查集{


    public 并查集_QuickUnion(int capacity) {
        super(capacity);
    }

    @Override
    public int find(int v) {
        rangCheck(v);
        //通过parent链条不断向上找
        //一直向上找到根节点为止
        while (v != parents[v]){
            v = parents[v];
        }
        return v;
    }

    @Override
    public void union(int v1, int v2) {

        int p1 = find(v1);
        int p2 = find(v2);
        if (p1 == p2) return;

        //将v1的根节点嫁接到v2的根节点即可
        parents[p1] = p2;
    }
}
